using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace IPAddress
{
    public class RandomRange
    {
        private readonly List<IntRange> m_Ranges = new List<IntRange>();

        public void Include(int min, int max)
        {
            RemoveRangesBetween(min, max);

            int minIndex = GetIndex(min - 1);
            int maxIndex = GetIndex(max + 1);

            if (minIndex >= 0 && maxIndex >= 0)
            {
                if (minIndex != maxIndex)
                {
                    int finalMax = m_Ranges[maxIndex].Max;
                    m_Ranges.RemoveAt(maxIndex);
                    m_Ranges[minIndex].Max = finalMax;
                }
            }
            else if(minIndex >= 0)
            {
                m_Ranges[minIndex].Max = max;
            }
            else if (maxIndex >= 0)
            {
                m_Ranges[maxIndex].Min = min;
            }
            else
            {
                m_Ranges.Add(new IntRange(min, max));
            }
        }

        public void Exclude(int min, int max)
        {
            RemoveRangesBetween(min, max);

            int minIndex = GetIndex(min);
            int maxIndex = GetIndex(max);

            if (minIndex >= 0 && maxIndex >= 0 && minIndex == maxIndex)
            {                
                m_Ranges.Add(new IntRange(m_Ranges[minIndex].Min, min - 1));
                m_Ranges.Add(new IntRange(max + 1, m_Ranges[minIndex].Max));
                m_Ranges.RemoveAt(minIndex);
            }
            else 
            {
                if (minIndex >= 0)
                {
                    m_Ranges[minIndex].Max = min - 1;
                }
                else if (maxIndex >= 0)
                {
                    m_Ranges[maxIndex].Min = max + 1;
                }
            }
        }

        private void RemoveRangesBetween(int min, int max)
        {
            for(int i = 0; i < m_Ranges.Count; i++)
            {
                if (m_Ranges[i].Min >= min && m_Ranges[i].Max <= max)
                {
                    m_Ranges.RemoveAt(i);
                    i--;
                }
            }
        }

        private int GetIndex(int value)
        {
            for (int i = 0; i < m_Ranges.Count; i++)
            {
                if (value >= m_Ranges[i].Min && value <= m_Ranges[i].Max)
                {
                    return i;
                }
            }

            return -1;
        }

        public IEnumerator GetEnumerator(int seed)
        {
            m_Ranges.Sort();

            SortedDictionary<RangeReference, IntRange> sd = new SortedDictionary<RangeReference, IntRange>();

            int index = Int32.MinValue;
            int indexEnd = Int32.MinValue;
            for (int i = 0; i < m_Ranges.Count; i++)
            {
                indexEnd = index + (m_Ranges[i].Max - m_Ranges[i].Min);
                m_Ranges[i].Offset = index;
                sd.Add(new RangeReference(index, indexEnd), m_Ranges[i]);                
                index = indexEnd + 1;
            }

            Random r = new Random(seed);

            if(Int32.MinValue == indexEnd)
            {
                yield break;
            }

            while(true)
            {
                int rnd;
                if(indexEnd == Int32.MaxValue)
                {
                    rnd = r.Next(Int32.MinValue, Int32.MaxValue);
                }
                else
                {
                    rnd = r.Next(Int32.MinValue, indexEnd + 1);
                }

                IntRange lr = sd[new RangeReference(rnd)];
                yield return lr.Min + (rnd - lr.Offset);                
            }
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();

            foreach (IntRange range in m_Ranges)
            {
                sb.AppendLine(String.Format("{0}, {1}", range.Min, range.Max));
            }

            return sb.ToString();
        }

        private class IntRange : IComparable<IntRange>
        {
            private int m_Min;
            private int m_Max;

            private int m_Offset;

            public int Min
            {
                get { return m_Min; }
                set { m_Min = value; }
            }

            public int Max
            {
                get { return m_Max; }
                set { m_Max = value; }
            }
            
            public int Offset
            {
                get { return m_Offset; }
                set { m_Offset = value; }
            }

            public IntRange(int min, int max)
            {
                m_Min = min;
                m_Max = max;
            }

            public int CompareTo(IntRange other)
            {
                if (m_Min > other.m_Min
                    && m_Max > other.m_Max)
                {
                    return 1;
                }
                else if (m_Min < other.m_Min
                         && m_Max < other.m_Max)
                {
                    return -1;
                }
                else
                {
                    return 0;
                }
            }
        }        
    }
}